#include <iostream>
#include <cassert>
using namespace std;
//思考：创建一个二叉搜索树，首先要构造树的节点，其次再实现树的结构
//创建树的节点时，必须思考节点内部应该包含哪些变量？
// 1. 节点代表的值，2. 节点指向左右子树的指针，3. 指向父亲节点的指针
//开始构建树的节点，我们希望节点内部的成员可以被外界使用，所以使用struct类
template <class V>
struct BSTreeNode
{
    BSTreeNode(const V& val)
        : _val(val)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
    {}
    V _val;
    BSTreeNode<V>* _left;
    BSTreeNode<V>* _right;
    BSTreeNode<V>* _parent;
};
template <class V>
class Comp
{
public:
    bool operator()(const V& v1, const V& v2)
    {
        return v1 < v2;
    }
};
template<>
class Comp<string>
{
public:
    bool operator()(const string& s1, const string& s2)
    {
        return s1 > s2;
    }
};

//构造完节点，下一步去设计树的结构，我们希望二叉搜索树只对外界展现成员函数，所以使用class类
template <class V, class Comp = Comp<V>>
class BSTree
{
public:
    typedef BSTreeNode<V> Node;

    //插入
    bool insert(const V& val)
    {
        //空树
        if(_root == nullptr)
        {
            _root = new Node(val);
            return true;
        }
        //非空树
        else
        {
            Comp comp;
            Node* cur = _root;
            Node* parent = nullptr;
            while(cur)
            {
                if(comp(val, cur->_val))
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(comp(cur->_val, val))
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    cout << "不允许插入已有的数据" << endl;
                    return false;
                }
            }

            //已经找到插入节点的父亲节点，开始判断插入左边还是右边
            Node* newnode = new Node(val);

            // 比根小，去左边插入
            if(comp(val, parent->_val))
            {
                parent->_left = newnode;
            }
            // 比根大，去右边插入
            else
            {
                parent->_right = newnode;
            }
            newnode->_parent = parent;
            return true;
        }
    }
    //删除
    bool erase(const V& val)
    {
        //没有节点了
        assert(size() > 0);

        Node* del_node = find(val);

        //1. 被删除节点不存在
        if(del_node == nullptr)
            return false;

        //2. 被删除节点只有左孩子/只有右孩子/左右孩子都没有
        else if(del_node->_left == nullptr || del_node->_right == nullptr)
        {
            //删除节点为根结点
            if(del_node == _root)
            {
                _root = del_node->_left == nullptr ? del_node->_right : del_node->_left;
                delete del_node;
                return true;
            }

            //不为根结点
            Node* parent = del_node->_parent;
            //只有左孩子
            if(del_node->_left != nullptr)
            {
                if(parent->_left == del_node)
                {
                    parent->_left = del_node->_left;
                }
                else
                {
                    parent->_right = del_node->_left;
                }
                del_node->_left->_parent = parent;
            }
            //只有右孩子
            else if(del_node->_right != nullptr)
            {
                if(parent->_left == del_node)
                {
                    parent->_left = del_node->_right;
                }
                else
                {
                    parent->_right = del_node->_right;
                }
                del_node->_right->_parent = parent;
            }
            //为叶节点，要处理叶节点的父亲节点被删除的孩子置为空
            else
            {
                parent->_left == del_node ?
                parent->_left = nullptr:
                parent->_right = nullptr;
            }
            delete del_node;
            del_node = nullptr;
        }
        //3. 被删除节点有左右孩子
        else
        {
            //这里只实现找左子树的最右节点，另外的方法大家自行实现
            Node* find_LT_right = del_node->_left;
            while(find_LT_right->_right)
            {
                find_LT_right = find_LT_right->_right;
            }
            //交换值
            swap(find_LT_right->_val, del_node->_val);
            //删除叶节点

            //删除之前，要让其父节点的被删除孩子指向空
            //这里不是父节点的右孩子原因：左子树只有一个节点
            find_LT_right == find_LT_right->_parent->_left ?
            find_LT_right->_parent->_left = nullptr
            : find_LT_right->_parent->_right = nullptr;

            delete find_LT_right;
            find_LT_right = nullptr;
        }
        return true;
    }
    //查找
    Node* find(const V& val)
    {
        Comp comp;
        Node* cur = _root;
        while(cur)
        {
            if(comp(val, cur->_val))
            {
                cur = cur->_left;
            }
            else if(comp(cur->_val, val))
            {
                cur = cur->_right;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }
    //中序遍历 -》 有序
    void inorder()
    {
        _inorder(_root);
        cout << endl;
    }
    //节点个数
    size_t size()
    {
        return _size(_root);
    }
    //求高度
    size_t height()
    {
        return _height(_root);
    }
private:
    Node* _root = nullptr; //这里使用指针的原因是动态的增删查改
    void _inorder(Node* root)
    {
        if(root == nullptr)
            return;
        _inorder(root->_left);
        cout << root->_val << " ";
        _inorder(root->_right);
    }
    size_t _size(Node* root)
    {
        if(root == nullptr)
            return 0;

        return _size(root->_left) + _size(root->_right) + 1;
    }
    size_t _height(Node* root)
    {
        if(root == nullptr)
            return 0;

        //求左子树的高度
        size_t left = _height(root->_left);
        //求右子树的高度
        size_t right = _height(root->_right);

        //返回左右子树最大的高度，作为树的高度
        return left > right ? left + 1 : right + 1;
    }
};